A CAM compares input data (search data) with stored data, and outputs an address of matched stored data. In general, a CAM carries out this comparing operation in parallel for all the stored data, and thus, data can be searched at high speed. A CAM having such a function is used in a wide range of fields, and, for example, used in a network router or a cache memory.
As a storage element of a CAM, a CAM cell based on a static random access memory (SRAM) is widely known. As CAM cells, one that can store two logic states of “0” and “1” and one that can store three logic states of “0”, “1”, and “X” are known. The former is referred to simply as a CAM cell or a binary CAM cell, and the latter is also referred to as a ternary CAM (TCAM) cell. A bit in the “X” state means “Don't care”, and, regardless of whether “0” is input or “1” is input as the search data, the data is regarded as matched.
Those CAM cells based on an SRAM can search data at high speed, for example, in several nanoseconds. On the other hand, in the search operation, all the storage words are required to be activated with regard to an input search word and are required to be bit-compared, and thus, operating power is very high.
As a method of reducing power consumption of the CAM in the search operation, in Non Patent Document 1, there is disclosed a method in which search operation is divided into several cycles to be carried out in a pipeline manner, and, with regard to a word that is determined to be mismatched earlier, no more bit comparison is made. According to this method, a CAM cell array including a plurality of word circuits each having an n-bit CAM cell is divided into several segments, and bit comparison is made for each segment. With regard to a word that is determined to be matched earlier, bit-comparing operation in the next segment is activated. On the other hand, with regard to a word that is determined to be mismatched, bit-comparing operation in the next segment is not carried out. By repeating sequentially the operation described above, useless bit search operation can be eliminated. Although time necessary for the search operation increases, the operating power can be significantly lowered.